package pen_exam.weilai_2024_03_12;


import java.util.Scanner;

//arr中 选择一个子序列 a1 < a2 < a3 且 互为整数倍，求最短子序列长度
public class Class01_MaxLenbeishu {
    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = Integer.parseInt(sc.nextLine());
//        String[] str = sc.nextLine().split(",");
//        int[] arr = new int[n];
//        for(int i = 0;i < n;i++){
//            arr[i] = Integer.parseInt(str[i]);
//        }
        int[] arr = {1,2,4,1};
        System.out.println(num(arr));
    }
    public static int num(int[] arr){
        if(arr == null && arr.length == 0){
            return 0;
        }

        return process(arr,0,arr.length - 1,Integer.MAX_VALUE,Integer.MIN_VALUE);
    }
    public static int process(int[] arr,int L,int R,int l,int r){
      if(L > R){
          return 0;
      }
      if(L == R && ((l == Integer.MAX_VALUE && r == Integer.MIN_VALUE)||((arr[R] != r)&&(arr[L] != l)&&(arr[L] & l) == 0 && (arr[L] & r) == 0))){
          return  1;
      }else
      if(L == R){
          return 0;
      }
      //1.左右都要 2.要左 3.要右4.都不要
      int p1 = 0;
      int p2 = 0;
      int p3 = 0;
      int p4;
      //左右
      if(l == Integer.MAX_VALUE && r == Integer.MIN_VALUE  && arr[R] != arr[L] &&  arr[R] % arr[L] == 0){
          p1 = 2 + process(arr,L + 1,R - 1,arr[L],arr[R]);
      }else if(arr[L] < arr[R] && r > l && r % l == 0 && arr[L] % l == 0 && r % arr[R] ==0 && arr[L] > l && arr[R] < r){
          p1 = 2 + process(arr,L + 1,R - 1,arr[L],arr[R]);
      }
      //左
      if((l == Integer.MAX_VALUE) ||( arr[L] != l && arr[L] % l == 0)){
          p2 = 1 + process(arr,L + 1,R,arr[L],r);
      }
      //右
      if((r == Integer.MIN_VALUE) ||( arr[R] != r && r % arr[R] == 0)){
         p3 = 1 + process(arr,L,R - 1,l,arr[R]);
      }
      //左右都不要
      p4 = process(arr,L + 1,R - 1,Integer.MAX_VALUE,Integer.MIN_VALUE);
      return Math.max(p1,Math.max(p2,Math.max(p3,p4)));
    }

}
